%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Representing Program Execution Behavior}~\label{chap:methodology}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Recent work in simulation concentrates on extracting
representative regions of a program to reduce the amount of
simulation.  The PinPoints~\cite{pp-1} tool characterizes an entire run of
a program and then uses the SimPoint~\cite{simpoint-1, simpoint-2} methodology to choose the
representative portions of the program. These systems are
effective for simulation as well as capable of modeling full
program execution.

A framework for workload characterization, modeling and run-time
optimization requires a flexible and efficient representation of
program execution. This chapter presents the structure and
methodology of the \textit{Cardinal Execution Map} (CEM). After
describing the development of the CEM, analysis of the resulting CEMs
from the SPEC2000 benchmarks~\cite{spec:2000} is presented.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Cardinal Terminology}~\label{sec:methtermonology}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The following is key terminology used throughout the remainder of this
thesis:

\begin{description}

    \item[Stage] A stage is a specific interval of a program's
execution. A single execution of a program is made up of a number
of sequential stages. Stages can be based on any metric such
as, but not limited to, instruction count or execution time.

    \item[Stage Characterization] Once a program is partitioned into
stages, each stage is individually characterized. This
characterization can be done with one of many measurements. Examples
include basic block execution or performance counter data
collection. All stages are characterized using the same metric.

    \item[Program Node] A program node represents a unique portion on
of the execution. The program nodes are found by performing a
clustering algorithm on the stage characterizations. The clustering is
done through a similarity score between characterizations. One program
node is then assigned to each cluster.

    \item[Stage Label] Once the program nodes are found, each is given
a unique label. This label is then given to all of the stages that
make up the cluster that the node represents.

    \item[Stage Timeline] The stage timeline is the sequence of stage
labels in program order.

    \item[Stage Transition] A stage transition refers to the changing
of one stage to the next in the program's execution.

    \item[Stage Path] A stage path is made of up one or more stage
transitions.

    \item[Cardinal Execution Map (CEM)] A CEM is a directed graph -
G(V,E) - with the vertices being the program nodes and the edges being
the unique stage transitions found in the stage timeline. The labels
for the edges are the number of times that transition is found in the
timeline.

\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Cardinal Execution Map Construction}~\label{sec:meth_exe-create}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The terms above form a natural progression in the creation of a
CEM. Figure~\ref{fig:exemap_example} shows the steps taken to create a
CEM for a fictitious program. The following subsections go into
detail about each step in the process.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.35]{fig/stages} \\
            \hspace{10pt}(a) \textit{Divide the program into sequential stages.}
        \end{minipage} \\
        \begin{minipage}{\textwidth}
            \centering
            \vspace{0.1in}
            \includegraphics[scale=0.35]{fig/stages_char} \\
            \hspace{10pt}(b)\textit{Characterize each stage.}
        \end{minipage} \\
        \begin{minipage}{\textwidth}
            \centering
            \vspace{0.1in}
            \includegraphics[scale=0.35]{fig/stages_cluster} \\
            \hspace{10pt}(c) \textit{Perform clustering using similar
                characterizations.}
        \end{minipage} \\
        \begin{minipage}{\textwidth}
            \centering
            \vspace{0.1in}
            \includegraphics[scale=0.35]{fig/stages_timeline} \\
            \hspace{10pt}(d) \textit{Assign the labels to the stages and create the timeline
                with transitions.}
        \end{minipage} \\
        \begin{minipage}{\textwidth}
            \centering
            \vspace{0.1in}
            \includegraphics[scale=0.35]{fig/stages_exemap} \\
            \hspace{10pt}(e) \textit{Use the clusters as nodes and stage
transitions as edges to create a graph representation of program execution.}
        \end{minipage} \\
    \end{tabular}
    \caption{Cardinal Execution Map creation.}
\label{fig:exemap_example}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Stages and Characterization}~\label{sec:meth_stages-char}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The first step in creating a CEM is to designate program stages.
For this work, program stages are determined by a
predefined number of instructions so that each stage has the same
instruction count. This approach is used in the PinPoints
toolchain for determining simulation points.

The first step in the PinPoints methodology is to profile the run of a
program by splitting it up into what are called program slices. Each
slice is comprised of a predetermined number of instructions. The size
of the slice is an important consideration. The slice size must be an
appropriate number of instructions so as to capture the behavior of
the program. Previous analysis~\cite{bbv-2, pgss-sim} shows that a slice
size between 1 million and 100 million instructions is appropriate for the
SPEC2000 benchmarks. The data results presented in this
thesis use 1 million instruction or 10 million instruction slices. For this
work, the term stage is synonymous with the term slice.

Once the program stages are determined, the characterization of each stage is
defined. This work uses the execution count of a program's basic blocks for
characterization. The term
basic block defines a group of assembly instructions that
has exactly one entry point and one exit point.
A basic block vector (BBV)~\cite{bbv-1} summarizes
the code points executed in a certain portion of
program execution and is well suited to characterize stages. Along with dividing
a program into stages, the PinPoints profiling step tracks each basic block that
executes during a slice and its contribution in terms of instruction count to
the slice, creating a BBV.

Since programs are made up of many basic blocks,
an issue with the BBV in this form is the high
dimensionality of the BBV. To deal with this issue, a hashing function
is used to project the high dimensional data into fewer dimensions. To
accomplish the projection, bits from the program counter of the first
instruction of the basic block are taken and used as an index into an
array. Each entry in the array is referred to a bin and holds a
running count of instructions for the basic blocks that are projected
to that bin. Figure~\ref{fig:hash_projection}(a) shows how the hashing
is done.

The result is a new BBV where the entries are the bins. The bins with
higher instruction counts represent the code points that executed the
most. For the purpose of comparison, the vector is minimized
further. Figure~\ref{fig:hash_projection}(b) shows the pseudo-code for
how this minimization is done. The result is the assignment of a 0 or
1 to each bin. Those bins with the highest instruction counts are
assigned a 1 and others 0 resulting in a bit vector. This bit vector is called
the Cardinal Profile BBV (CP-BBV).

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
        \centering
            \includegraphics[scale=0.35]{fig/hash_projection} \\
            \vspace{-0.5in}
            \hspace{10pt}(a) \textit{Hashing Projection.}
        \end{minipage} \\\\
        \begin{minipage}{\textwidth}
            \centering
            \begin{verbatim}
                cutoff = scaling_factor / num_bins;
                for(i = 0; i < num_bins; i++) {
                  bin[i] = bin[i] / stage_size;
                  if(bin[i] >= cutoff)
                      bin[i] = 1;
                  else
                      bin[i] = 0;
                }
            \end{verbatim}
        \hspace{10pt}(b) \textit{Reducing the bins to a bit vector.}
        \end{minipage} \\
    \end{tabular}
    \caption{Reducing the BBV from a high dimensional representation into a more
manageable form.}
\label{fig:hash_projection}
\end{figure}

Figure~\ref{fig:raw_bbv_compare} shows actual data taken from three
stages of 164.gzip and showing how the raw BBV is reduced and
compared.  Figure~\ref{fig:raw_bbv_compare}(a) shows the distribution
of basic blocks executed in each stage. With the stage size being one
million instructions, the y-axis indicates the number of instructions
that basic block executed. The x-axis simply shows the basic blocks
numbered from 1 to 1000. Stage A has two main areas of execution
around basic blocks 100 and 600. Stages B and C share execution near
basic block 200. All three stages show execution around 600, but Stages
A and B show more execution.

Figure~\ref{fig:raw_bbv_compare}(b) shows the actual bit vectors that
are derived for these stages. The vectors share a value of 1 which
indicates the shared regions of
execution. Figure~\ref{fig:raw_bbv_compare}(c) shows the Hamming
distance comparison between the three stages. This diagram shows that
Stages B and C are most similar whiles Stage A and C are the least similar.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=1]{fig/slice_raw_basic_block} \\
            \hspace{10pt}(a) \textit{Instruction counts for the basic blocks of
                three stages of 164.gzip.}
        \end{minipage} \\\\
        \begin{minipage}{\textwidth}
            \centering
            \begin{align*}
                Stage\ A: 00000000000100100000000000001001 \\
                Stage\ B: 00000000000000000000100000101000 \\
                Stage\ C: 00000000000000000000100000100000 \\
            \end{align*}
            \hspace{10pt}(b) \textit{Bit vectors for the three stages.}
        \end{minipage} \\
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.25]{fig/hamming_dist} \\
            \hspace{10pt}(a) \textit{Hamming distance between Stages A, B and C.}
        \end{minipage} \\\\
    \end{tabular}
    \caption{Creation and comparison of the CP-BBV.}
\label{fig:raw_bbv_compare}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Program Nodes}~\label{sec:meth_nodes}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

After stage characterization, the CP-BBVs are compared to form
clusters of similar CP-BBVs. Since
each CP-BBV is represented by a bit vector, they can be compared easily
using the Hamming distance. With a predetermined tolerance, the
hamming distance is used to generate the similarity score for
clustering. A pivot clustering algorithm, as described in~\cite{cogs-sim}, is
used to find the program nodes.

The basic algorithm of pivot clustering starts with zero
clusters. The first sample is assigned to the first cluster. If the
second sample is similar to the first item, it is assigned to that
cluster and if it is not similar, it starts another cluster. This process
continues until all the samples are assigned to a cluster. The list of
items is traversed only once so each item is processed only once.

The pivot clustering algorithm has advantages and disadvantages. A
disadvantage to pivot clustering is that an item may not end up in the
cluster it is most similar to since each item is processed once. Since
this is the case, pivot clustering may not be as accurate as other
algorithms such as k-means~\cite{k-means}. On the other hand, pivot
clustering is much faster. As pivot clustering can cluster
samples quickly as they become available, the clustering method may have the
best potential for use in a dynamic system.

The result of clustering is a set of program nodes
that represent the entire program. Each node is assigned a unique label and
includes the set of program stages determined by clustering.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Timeline and Graph}~\label{sec:meth_timeline-graph}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

With each stage labeled, the program timeline can be represented by listing each
stage's label in program order.
The CEM is a directed graph G(V,E) where V is the set of program
nodes and E is the set of unique transitions in the timeline. Each
edge e in E is labeled with its number of occurrences in the timeline.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Types of CEMs}~\label{sec:meth_types}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The CEM can be used to represent portions of a program, a single run of a program
or many runs of a program. The CEM can also be used to represent the threads in a
multi-threaded program. This section presents three different formations of CEMs
resulting from modern computing environments.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Base CEM - Single Program Input Profile}~\label{sec:meth_single-input}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The simplest CEM is that of a single run of a program and is called a
Base CEM. A Base CEM shows the different program nodes and the
transitions taken between those nodes for a single run of a program.
Figure~\ref{fig:exemap_177_mesa_single_input} shows the Base CEM for
the SPEC2000 benchmark 177.mesa which is a 3-D graphics library.
The Base CEM contains 6 nodes with
many transitions between these nodes. Node 0 only has one out going
edge so it is clear that this is the beginning of the program. The
program goes on to Node 1 where it executes 212 times. This may be
considered the initialization portion of the run. Next, the program transitions
between Nodes 2, 3 and 4. Presumably, this constitutes the computation portion
of the program. Lastly, the execution transitions to Node 5 and does
not return. This is the end of the program and is likely some the
termination portion of the program.

Not all of the CEMs are this clean with only 6 nodes. As will be seen
in Section~\ref{sec:meth_results} CEMs vary widely in the number of
nodes and edges.  Appendix~\ref{app:exe_maps} contains the Base CEMs for all of
the inputs of the SPEC2000 programs.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.35]{fig/177_mesa_ref_0} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Base CEM for 177.mesa.}
\label{fig:exemap_177_mesa_single_input}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Composite CEM - Integrating Multiple Input Profiles}~\label{sec:meth_multi-input}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

While the Base CEM represents a single run of a program, a Composite
CEM integrates multiple profiles. The Composite CEM demonstrates
common stage paths and profile-specific code
points. Figures~\ref{fig:exemap_252_eon_comp}(a)-(c) show the Base
CEMs for three inputs of the benchmark
252.eon. Figure~\ref{fig:exemap_252_eon_comp}(d) shows the Composite
CEM for 252.eon. Using the same binary to run multiple inputs of an
program, the CP-BBVs can be directly compared across those runs. In
this case, nodes and edges that can be shared between different
executions of the program. In Figure~\ref{fig:exemap_252_eon_comp}(d)
gray nodes are shared between at least two inputs. Edges that
are black are shared between at least two inputs. Nodes and edges of different
colors are unique to a single input. Node 7 in this
figure is a node that is unique to one of the inputs. Edges from 4 to 5 and 7 to
3 are transitions that are unique to a single input.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
        \centering
            \includegraphics[scale=0.33]{fig/252_eon_ref_0} \\
            \hspace{10pt}(a) \textit{Base CEM for 252.eon reference input 0.}
        \end{minipage} \\
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.33]{fig/252_eon_ref_1} \\
            \hspace{10pt}(b) \textit{Base CEM for 252.eon reference input 1.}
        \end{minipage} \\
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.33]{fig/252_eon_ref_2} \\
            \hspace{10pt}(c) \textit{Base CEM for 252.eon reference input 2.}
        \end{minipage} \\
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.33]{fig/252_eon_composite} \\
            \hspace{10pt}(d) \textit{Composite CEM for 252.eon reference inputs 0, 1 and 2.}
        \end{minipage} \\
    \end{tabular}
    \caption{Composite CEM for three reference inputs of 252.eon.}
\label{fig:exemap_252_eon_comp}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Composite CEM - Integrating Multiple Thread Profiles}~\label{sec:meth_multi-thread}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Another type of Composite CEM shows all threads of a multi-threaded
program in one graph. Figure~\ref{fig:exemap_fft_splash} shows the CEM
for a 4-threaded run SPLASH2~\cite{splash2} program fft. Using this CEM,
a data decomposition model can be seen. The main thread which
is responsible for initialization and partitioning of the data begins
the program. Next, the threads are spawned and all threads work on the
data.  Finally, when the threads complete their computations the
program is terminated.

Looking at the CEM representation for this, two thread unique nodes,
1 and 0, start the program. These nodes
represent the work the main thread is doing to initialize the data and spawn the
threads. Next, the four shared nodes 2, 3, 4 and 5 represent the
common work being done by all of the threads.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.35]{fig/fft_4_composite} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Composite CEM for a 4 thread run of the SPLASH2 benchmark fft.}
\label{fig:exemap_fft_splash}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Program Analysis Using CEMs}~\label{sec:meth_results}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This section analyzes the CEMs resulting from the SPEC2000 benchmark
suite.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Single Input Evaluation}~\label{sec:meth_single_input}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The run-time behavior of a program can be categorized by a number
of performance and execution indicators.  For instance, the number of
distinct phases of execution indicates a potential for variation as
well as a prediction rate of future behavior at specific program
points.  The Base CEMs are effective in demonstrating
behavioral trends when the SPEC2000 benchmarks are examined.
In general, the integer benchmarks result in larger CEMs that have
more traversals per node. The floating point programs tend to
involve fewer but long-running phases each including a number of
computationally-intensive loops. The
raw data for all of the SPEC2000 benchmarks is shown in
Appendix~\ref{app:raw_data}.

Figure~\ref{fig:node_contrib_2000} shows node contributions for the
SPEC2000 benchmarks. Figure~\ref{fig:node_contrib_2000}(a) shows the
results for the integer benchmarks and
Figure~\ref{fig:node_contrib_2000}(b) shows the results for the floating
point benchmarks. One reference input for each program is included
in the graphs. The x-axis represents the nodes organized
from the highest occurring nodes to the lowest occurring nodes. The
y-axis represents the percentage of overall execution. The graph shows
how much of the execution is represented when starting from the
highest occurring node and working toward the lowest occurring
nodes. Some nodes only occur a few times and thus, do not contribute
to much of the overall execution.

To encompass 80\% of program execution, all but one of the integer benchmarks
require no more than 12 nodes while all but one of the floating point benchmarks
require no more than seven nodes. Since few nodes are required to represent a
large portion of the program, the CEM representation shows an ability to
represent the program execution in a condensed manner.

\begin{figure}[t!]
    \centering
    \begin{tabular}{cc}
        \centering
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.25]{fig/node_contrib_2000int}
        \hspace{2pt}
        \end{minipage} &
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.25]{fig/node_contrib_2000fp}
        \end{minipage}
        \\  (a) \textit{SPEC2000 integer programs.} &
            (b) \textit{SPEC2000 floating point programs.}
    \end{tabular}
    \caption{Node contributions for the SPEC2000 benchmarks.}
    \label{fig:node_contrib_2000}
\end{figure}

Another way to look at the representation is in terms of the stage
paths that are found in the timeline. The number of unique paths
indicates the number of patterns found in the execution of a
program. Table~\ref{table:stage_path_5} in Appendix~\ref{app:raw_data}
shows the total number of stage paths of length five found in each
program. The table also reports the number of unique paths in the
total set of stage paths as a count and a percentage of the total
paths. With the exception of 176.gcc, 186.crafty, 255.vortex and
256.bzip2 the unique paths are less than 10\% of the total paths.  In
some cases it is less than 1\%.

With the number of unique paths being far less than the total number
of paths, it is interesting to look at how many paths contribute to the
total execution of a program. Figure~\ref{fig:path_5_contrib} shows
plots which depict how many paths contribute to the overall execution
of the SPEC2000 programs. The x-axis shows the percentage of top
occurring stage paths while the y-axis shows the corresponding contribution to the
overall execution.

Figure~\ref{fig:path_5_contrib}(a) shows the contributions for one
reference input for all of the SPEC2000 benchmarks. Taking only the
top 10\% of the 5-stage paths, over 60\% of the overall execution is
represented. Many of these runs require only 10-20\% of the top paths
to represent over 90\% of the execution.

Figures~\ref{fig:path_5_contrib}(b)-(f) show the results of different
inputs to the same program. All of the programs show a difference
among the inputs.  164.gzip and 252.eon show the inputs converging at
about the same point while 176.gcc, 253.perlbmk and 256.bzip2 seem
only to converge once all paths are included.

\begin{figure}[h!]
    \centering
    \begin{tabular}{cc}
        \centering
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.24]{fig/path_5_2000_ref_0}
        \hspace{2pt}
        \end{minipage} &
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.24]{fig/path_5_164_gzip}
        \end{minipage}
        \\  (a) \textit{All SPEC2000 benchmarks one input.} &
            (b) \textit{5 reference inputs for 164.gzip.}
    \end{tabular}
    \begin{tabular}{cc}
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.24]{fig/path_5_176_gcc}
        \hspace{2pt}
        \end{minipage} &
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.24]{fig/path_5_252_eon}
        \end{minipage}
        \\  (c) \textit{5 reference inputs for 176.gcc.} &
            (d) \textit{3 reference inputs for 252.eon.}
    \end{tabular}
    \begin{tabular}{cc}
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.24]{fig/path_5_253_perlbmk}
        \hspace{2pt}
        \end{minipage} &
        \begin{minipage}{0.5\textwidth}
        \centering
        \includegraphics[scale=0.24]{fig/path_5_256_bzip2}
        \end{minipage}
        \\  (e) \textit{7 reference inputs for 253.perlbmk.} &
            (f) \textit{3 reference inputs for 256.bzip2.}
    \end{tabular}
    \caption{Contribution of 5 stage paths for programs from the SPEC2000
benchmark suite.}
    \label{fig:path_5_contrib}
\end{figure}

Looking at the graphs in Appendix~\ref{app:exe_maps} many different
formations can be seen. Some graphs exhibit loop-backs with high
counts representing portions of the program spent in one code
region. Other graphs show many edges with smaller counts illustrating
an program that bounces between code regions.

The composition of these paths can indicate the the general form of
the graph for the program. Paths of length five can be composed
of stages from one node, two nodes, three nodes, four nodes or five
nodes. Those paths that are made up of stages from a single node
represent loop-backs in the graph. Those paths that are made up of
multiple labels represent portions of the program that bounce between
code regions.

Figure~\ref{fig:path_composition} shows the composition
of all paths of length five in one reference input of the
SPEC2000 benchmarks. The left side of the graph shows the integer
programs while the right side of the graph shows the floating point
programs.

Looking at this graph, many different compositions can be seen. A
majority of the paths in the integer benchmarks are composed one or
two labels. Few of these programs are made up of only one stage
label. Looking at the floating point benchmarks, seven out of the 13
programs show almost all paths being composed of one stage
label. As alluded to earlier, this shows the loop-centric nature of
the floating point benchmarks. Two of the programs, 197.parser
and 179.art, show the most distribution from one to five label
paths. The behavior of these programs would be execution in
many different code regions.


\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.5]{fig/path_compostion_spec2000} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Composition of paths of length 5 for the SPEC2000 benchmarks.}
\label{fig:path_composition}
\end{figure}

%\begin{figure}[ht!]
%    \begin{tabular}{c}
%        \begin{minipage}{\textwidth}
%            \centering
%            \includegraphics[scale=0.5]{fig/path_contribution_5} \\
%        \end{minipage} \\
%    \end{tabular}
%    \caption{Contribution of 5 stage paths to overall execution.}
%\label{fig:path_contrib_5}
%\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Composite CEM Analysis}~\label{sec:meth_composite_cem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Those benchmarks that have more than one input can be represented by a
Composite CEM. Similarities in the runs are shown through the nodes
that are shared across different runs of the program. The more
shared nodes there are in the Composite CEM, the more similar runs are
across different inputs.

Figure~\ref{fig:2000_composite_nodes} shows a stacked bar graph
representing the shared and unique nodes for the composite graphs from
the SPEC2000 programs.  All but 175.vpr show at least 70\% of the
nodes to be shared by two or more runs of the program.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.5]{fig/spec2000_composite_nodes} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Node statistics for the SPEC2000 Composite CEMs.}
\label{fig:2000_composite_nodes}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Representative Nature of the CEMs}~\label{sec:meth_cem_representation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Previous work~\cite{simpoint-3} shows a correlation between code points
executed and the program behavior.  The CEM
representation allows for these characterizations to be tracked and
analyzed.  Figure~\ref{fig:164_gzip_stats_comp} shows three plots. The
top plot shows the stage labels over time while the second and third
plot show the IPC and L2 cache miss rate over time for each stage.  A
similar pattern in all three plots can be seen. This shows that the
labels assigned to the stages from the clusters track execution and is
a viable representation of the execution.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=1]{fig/164_gzip_stat_comp} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Comparing CEM states, processor IPC, and L2 miss rate for 164.gzip.}
\label{fig:164_gzip_stats_comp}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Comparing CEMs Across Compiler Transformation}~\label{sec:meth_cem_comp}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Compilers and compiler optimizations can substantially modify static code and run-time
behaviors of a program. CEMs have the ability to track these transformations.
Using graph theory, the CEMs for binaries resulting from different compilers and
complier optimizations are compared.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{GCC and ICC}~\label{sec:meth_icc_gcc}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

To study the effect of compiler development, the SPEC2000 integer benchmarks are complied
with the following configurations:

\begin{enumerate}

    \item GCC -O2

    \item GCC -O3

    \item ICC -O2

    \item ICC -O3

\end{enumerate}


Graph similarity~\cite{graphsim-zager, graphsim-blondel} and graph
clustering~\cite{graphcluster-bunke} are
effective methods for comparing the CEM representations Graph similarity assigns a score between
two graphs to reflect how similar they are while graph clustering forms sets of
similar graphs from a larger pool of graphs.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Graph Similarity}~\label{sec:meth_graph_sim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Using~\cite{graphsim-nyu} from NYU, the similarity
between the CEMs is computed. Table~\ref{table:graph_sim} shows the most similar
graphs for each of the 47 graphs (255.vortex compiled with GCC -O2 results in a
segmentation fault).

%\begin{table}[h!]
\begin{table}
\center
\scriptsize
\begin{tabular}{|p{1.5in}|p{1.5in}|p{0.5in}|p{1.0in}|}
\hline
    App&Most Similar&Score&Reverse Score\\
\hline\hline
    164.gzip-gcc-O2&256.bzip2-icc-O2, 256.bzip2-icc-O3&0.595&0.348, 0.348\\
\hline
    164.gzip-gcc-O3&164.gzip-gcc-O2, 181.mcf-gcc-O2&0.524&0.291, 0.422\\
\hline
    164.gzip-icc-O2&164.gzip-gcc-O2&0.517&0.419\\
\hline
    164.gzip-icc-O3&164.gzip-gcc-O2&0.535&0.311\\
\hline
    175.vpr-gcc-O2&186.crafty-gcc-O3&1.000&0.378\\
\hline
    175.vpr-gcc-O3&255.vortex-icc-O3&1.000&0.459\\
\hline
    175.vpr-icc-O2&175.vpr-icc-O3, 186.crafty-gcc-O3, 255.vortex-icc-O3&1.000&1.000, 0.356, 0.432\\
\hline
    175.vpr-icc-O3&175.vpr-icc-O2, 186.crafty-gcc-O3&1.000&1.000, 0.356\\
\hline
    176.gcc-gcc-O2&176.gcc-gcc-O3&0.430&0.456\\
\hline
    176.gcc-gcc-O3&254.gap-icc-O3&0.424&0.260\\
\hline
    176.gcc-icc-O2&176.gcc-icc-O3&0.419&0.394\\
\hline
    176.gcc-icc-O3&176.gcc-icc-O2&0.366&0.389\\
\hline
    181.mcf-gcc-O2&164.gzip-gcc-O2&0.588&0.405\\
\hline
    181.mcf-gcc-O3&164.gzip-gcc-O3&0.560&0.512\\
\hline
    181.mcf-icc-O2&181.mcf-icc-O3&1.000&1.000\\
\hline
    181.mcf-icc-O3&181.mcf-icc-O2&1.000&1.000\\
\hline
    186.crafty-gcc-O2&186.crafty-icc-O2, 186.crafty-icc-O3, 252.eon-gcc-O3, 253.perlbmk-icc-O2&1.000&0.688, 0.688, 0.478, 0.423\\
\hline
    186.crafty-gcc-O3&255.vortex-icc-O2, 255.vortex-icc-O3&0.822&1.000, 1.000\\
\hline
    186.crafty-icc-O2&186.crafty-icc-O3, 252.eon-gcc-O3&1.000&1.000, 0.696\\
\hline
    186.crafty-icc-O3&186.crafty-icc-O2, 252.eon-gcc-O3&1.000&1.000, 0.696\\
\hline
    197.parser-gcc-O2&197.parser-gcc-O3&0.660&0.689\\
\hline
    197.parser-gcc-O3&197.parser-icc-O2, 197.parser-icc-O3&0.704&0.643, 0.643\\
\hline
    197.parser-icc-O2&197.parser-icc-O3&1.000&1.000\\
\hline
    197.parser-icc-O3&197.parser-icc-O2&1.000&1.000\\
\hline
    252.eon-gcc-O2&252.eon-icc-O2, 252.eon-icc-O3&1.000&1.000, 1.000\\
\hline
    252.eon-gcc-O3&255.vortex-icc-O2, 255.vortex-icc-O3&0.957&0.595, 0.595\\
\hline
    252.eon-icc-O2&252.eon-gcc-O2, 252.eon-icc-O3&1.000&1.000, 1.000\\
\hline
    252.eon-icc-O3&252.eon-gcc-O2, 252.eon-icc-O2&1.000&1.000, 1.000\\
\hline
    253.perlbmk-gcc-O2&253.perlbmk-gcc-O3&0.714&0.758\\
\hline
    253.perlbmk-gcc-O3&253.perlbmk-gcc-O2&0.848&0.800\\
\hline
    253.perlbmk-icc-O2&186.crafty-gcc-O3&0.808&0.467\\
\hline
    253.perlbmk-icc-O3&186.crafty-gcc-O3&1.000&0.578\\
\hline
    254.gap-gcc-O2&254.gap-icc-O3&0.444&0.452\\
\hline
    254.gap-gcc-O3&197.parser-gcc-O3&0.425&0.095\\
\hline
    254.gap-icc-O2&197.parser-gcc-O3&0.488&0.098\\
\hline
    254.gap-icc-O3&197.parser-gcc-O3&0.432&0.082\\
\hline
    255.vortex-gcc-O3&255.vortex-icc-O2&1.000&0.649\\
\hline
    255.vortex-icc-O2&186.crafty-gcc-O3, 255.vortex-icc-O3&1.000&0.822, 1.000\\
\hline
    255.vortex-icc-O3&186.crafty-gcc-O3, 255.vortex-icc-O2&1.000&0.822, 1.000\\
\hline
    256.bzip2-gcc-O2&256.bzip2-gcc-O3&0.433&0.367\\
\hline
    256.bzip2-gcc-O3&256.bzip2-icc-O2, 256.bzip2-icc-O3&0.414&0.344, 0.344\\
\hline
    256.bzip2-icc-O2&256.bzip2-icc-O3&1.000&1.000\\
\hline
    256.bzip2-icc-O3&256.bzip2-icc-O2&1.000&1.000\\
\hline
    300.twolf-gcc-O2&164.gzip-gcc-O3, 186.crafty-gcc-O3, 253.perlbmk-gcc-O2&0.564&0.268, 0.489, 0.629\\
\hline
    300.twolf-gcc-O3&164.gzip-gcc-O3&0.564&0.268\\
\hline
    300.twolf-icc-O2&300.twolf-icc-O3&1.000&1.000\\
\hline
    300.twolf-icc-O3&300.twolf-icc-O2&1.000&1.000\\
\hline
\end{tabular}
\caption{CEMs with highest evaluated similarity score.}
\label{table:graph_sim}
\end{table}

The closer the score is to 1.000, the more similar the CEMs are. Comparing any
graph to itself results in a score of 1.000. The similarity is computed by
comparing the nodes in the graphs and the number of outgoing and incoming edges.
Table~\ref{table:graph_sim} shows that most of the time, the most similar graph is one
from the same program but a different compiler or optimization level. At the same
time, many of the graphs are also similar to graphs from other programs as
well.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Graph Clustering}~\label{sec:meth_graph_cluster}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Another way to look at the CEMs is to try and cluster them to see what groups
of CEMs are similar. The tool~\cite{graphcluster-nyu} from NYU takes a group of graphs and
performs a k-means clustering to group the graphs. The clustering tool is run
with a target of 13 clusters. With 12 programs and 13 clusters,
if the graphs from the programs are similar to each other but
not to other programs one would expect the 13 clusters to have roughly one
program each. The results from this clustering are shown in
Figure~\ref{fig:nyu_graph_cluster}.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.25]{fig/nyu_graph_cluster} \\
        \end{minipage} \\
    \end{tabular}
   \caption{Clustering CEMs across GCC and ICC using O2 and O3 flags.}
\label{fig:nyu_graph_cluster}
\end{figure}

The results show five clusters that contain three or four CEMs from one
program. One cluster resulted in 10 CEMs. In increasing the number of
clusters to 14 and beyond this cluster remained meaning that these CEMs are
very similar. Other clusters are composed of one or two programs showing
that some programs behave similarly in terms of the CEM.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Clustering Program Behaviors}~\label{sec:meth_graph_cluster_many}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Another way to attempt to see how similar the graphs are across binaries is to
take the CEMs created for many different binaries and perform graph clustering. To do this,
five programs are selected, 164.gzip, 176.gcc, 181.mcf, 254.gap and
300.twolf, and compiled with 53 different sets of flags using GCC-4.1. The
CEMs for these binaries are then created for the first reference input.

After all of the CEMs are created the same graph clustering tool as described
above is used to cluster the graphs. Figure~\ref{fig:nyu_graph_cluster_evolution}
shows results from clustering using five clusters up to 10 clusters.
The clusters show which programs and how many of each programs are
grouped together.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.25]{fig/graph_cluster_5_10} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Clustering CEMs across many different compiler optimizations.}
\label{fig:nyu_graph_cluster_evolution}
\end{figure}

Using five clusters results in one big cluster with 181.mcf, 164.gzip and
300.twolf. Moving out to six clusters, the 300.twolf graphs get moved into the
new cluster while the other clusters remain the same. The spreading of
programs continues going out to 10 clusters.

Even at the lower number of clusters the programs seem to split into
multiple groups showing that there are a couple of different forms the
CEMs can take depending on the compiler optimizations used. A
run-time system that stores CEM information for these programs would only
have to store a couple representations for each program to cover most any
binary the system may run for the programs.

Another way to look at the affect of the compiler flags on the clustering is to
see how the different flag versions cause the graphs to differ from the normal
program form. Figure~\ref{fig:nyu_graph_cluster_version_effect} shows for each
set of clusters, the number of versions that cause graphs to be located in a
cluster that does not have a majority of the graphs for a specific program.

\begin{figure}[ht!]
    \begin{tabular}{c}
        \begin{minipage}{\textwidth}
            \centering
            \includegraphics[scale=0.45]{fig/evolution_cluster_change_dist} \\
        \end{minipage} \\
    \end{tabular}
    \caption{Effect of compiler optimizations on clustering.}
\label{fig:nyu_graph_cluster_version_effect}
\end{figure}

Using cluster sizes of 5, 6 and 7 results in mostly just one or two programs
having graphs found outside the major cluster. A cluster size of 8 increases in both no
programs being affected and two programs being affected. Cluster sizes
of 9 and 10 start to show many compiler versions affecting three programs
and in some cases four or all five programs.
